package offerbook;


import utils.ListNode;
import utils.ListUtil;

/**
 * O(1)时间删除给定单向链表的节点.
 * 由于是单向链表，给定节点，如果删除一般需要知道前驱节点，这样
 * 才能改变前驱节点的next为删除节点的next。
 * 如果要遍历则需要O(n)。
 *
 * 换一种思路，将当前节点复制后面节点的val，然后删除后面节点，就等于
 * 知道了前驱节点.
 *
 * 注意几个特殊情况：list = null， head.next =  null, deleteNode = tail
 * @date 2020/3/8 23:12
 */
public class Code13_DeleteListNode {

    public static ListNode deleteListNode(ListNode head, ListNode node){
        if(head == null || node == null) return head;
        if(head.next == null) return null;
        //如果是尾巴节点，需要O(n)
        if(node.next == null){
            ListNode p = head;
            while (p != null){
                //p.next is the last node
                if(p.next.next == null){
                    p.next = null;
                    return head;
                }
                p = p.next;
            }
        }
        //否则是普通节点，
        node.val = node.next.val;
        node.next = node.next.next;
        return head;
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);

        ListUtil.printLinkedList(head1);
        ListUtil.printLinkedList(deleteListNode(head1,head1));
    }
}
